#define DEBUG
#include <cstdio>
#define MAXN 500000
#define MAXLOGN 18

using namespace std;

void sieve(int n, int *ua, int *pa) {
  static int book[MAXN+1];
  book[1]=true;
  ua[1]=1;
  for (int i=2; i<=n; i++) {
    if (!book[i]) {
      ua[i]=-1, pa[i]=1;
      for (int j=1; j<=n/i; j++) {
	book[i*j]=true;
	if (j%i) {
	  ua[i*j]=ua[j]*(-1);
	} else {
	  ua[i*j]=0;
	}
	pa[i*j]=pa[j]+1;
      }
    }
  }
}

int main() {
#ifdef DEBUG
  freopen("4379.in", "r", stdin);
  freopen("4379.out", "w", stdout);
#endif

  static int f[MAXLOGN+1][MAXN+1], ua[MAXN+1], pa[MAXN+1];
  sieve(MAXN+1, ua, pa);
  for (int i=1; i<=MAXN; i++) {
    for (int j=i; j<=MAXN; j+=i) {
      f[pa[i]][j]+=ua[j/i];
    }
  }
  for (int j=1; j<=MAXN; j++) {
    for (int i=1; i<=MAXLOGN; i++) {
      f[i][j] += f[i-1][j];
    }
  }
  for (int i=0; i<=MAXLOGN; i++) {
    for (int j=1; j<=MAXN; j++) {
      f[i][j] += f[i][j-1];
    }
  }

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    int n, m, p;
    scanf("%d %d %d", &n, &m, &p);
    if (p>MAXLOGN) {
      printf("%lld\n", (long long)n*m);
      continue;
    }
    if (n>m) {
      int temp=n;
      n=m, m=temp;
    }
    int ans=0;
    for (int i=1, j=1, last=0; i<=n && j<=m; ) {
      if (i<=j) {
	ans+=(n/i)*(m/i)*(f[p][i]-f[p][last]);
	last=i;
	i=i<n ? n/(n/(i+1)) : n+1;
      } else {
	ans+=(n/j)*(m/j)*(f[p][j]-f[p][last]);
	last=j;
	j=j<m ? m/(m/(j+1)) : m+1;
      }
    }
    printf("%d\n", ans);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
